Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Ja, gut. Ich hatte noch mal kurz da ein, wo wir letztes Mal aufgehört haben,

da habe ich so eine schnellere Merkung im Raum geworfen aus dem Klinisatz.

Folgt jetzt, dass reguläre Sprachen abgeschlossen sind unter Kompliment und Durchschnitt.

Das machen wir noch einmal etwas expliziter, als ich das letztes Mal formuliert hatte.

Und zwar zunächst mal Komplimentierung.

Komplimentierung werde ich auf deterministischen endlichen Automaten.

Und ich hatte letztes Mal angedeutet, dass es sehr leicht ist.

Ich nehme mir so einen Automaten und schreibe ihn gleich als Rundfunk-Pilip aus Zustandsmenge,

Alphabet, Zustandsübergangsfunktion, initialer Zustand und Menge finaler Zustände.

Und aus dem konstruiere ich einen Automaten, der genau das Kompliment der Sprache akzeptiert,

denn dieser hier ist nicht akzeptiert. Der sieht in fast allen Komponenten genauso aus wie der versprüngliche.

Nur die finalen Zustände, die ändere ich, das heißt, ich drehe es mal, was vorher final war, ist jetzt nicht mehr umgekehrt.

Und es ist schon klar, dass im deterministischen, wurde gemerkt, jeder Engel sich hier genau akzeptiert wird, wenn es da nicht akzeptiert wird.

Das ist aber nur deswegen so, weil das ein deterministischer Automat ist. Im nicht deterministischen klappt das nicht.

Deswegen erzähle ich es nochmal. Also im nicht deterministischen kann Folgendes passieren.

Ich habe hier so ein Wort U, das läuft irgendwie vom initialen Zustand zu einem Final und wird deswegen akzeptiert.

Und ich hoffe jetzt hier durch diese Konstruktion hier, wo ich den Akzeptanzstatus der Zustände immer umdrehe,

jetzt hier einen Automaten zu erzeugen, wo also U gerade nicht mehr akzeptiert wird.

Nun ist dieser hier aber nicht deterministisch, das heißt, das U, das kann durchaus auch etwas anderes verursachen.

Das kann also auch hier landen in einem Zustand, der nicht akzeptierend ist.

Und wenn ich dann diese Konstruktion mache, sieht das Bild noch genauso aus.

Der immer noch diese beiden Pfade in das Wort U nehmen kann, hat den Akzeptanzstatus jeweils umgedreht.

Der wird nun immer noch akzeptiert, weil das einen Zustand erreicht, der vorher nicht akzeptiert war und deswegen jetzt akzeptiert ist.

Das heißt, die Komplimentbildung ist an dieser Stelle glorios schiefgegangen, das heißt, das geht nicht.

Das beweist natürlich nicht, dass man nicht irgendwie anders nicht deterministische Automaten komplimentieren kann.

Und in der Tat wissen wir natürlich sofort, dass das geht, weil wir wissen, dass nicht deterministische Automaten eben von den Sprachen her,

die sie akzeptieren können, äquivalent sind zu den deterministischen.

Also wenn die deterministischen abgeschlossen sind unter Kompliment, müssen die nicht deterministischen das auch sein.

Nur, bei nicht deterministischen Automaten haben wir eben keine schlauere Methode als hier hier.

Wenn wir an, ich hätte so einen Automaten A, einen nicht deterministischen Automaten,

da kann ich ein Äquivalent, ein DFA zu bauen, per Protenzmengenkonstruktion,

der dieselbe Sprache akzeptiert.

Und dann kann ich, ich sollte das durch so ein Quer an, manchmal schreibt man ja Bucin-Algebrafe an, als Quer,

dann kann ich aus diesem DFA, kann ich jetzt einen Komplimentautomaten bauen, sofort, nämlich so wie da oben.

Aber dieser Komplimentierte Automat, der ist jetzt womöglich exponentiell größer, als der, wenn ich reingegangen bin,

denn diese Protenzmengenkonstruktion, mit der ich von A nach A strich,

verursacht nun mal eine exponentielle Vergrößerung meines Automaten.

Und das ist das Schlauste, was man für eine Komplimentierung von nicht deterministischen Automaten so sagen kann.

Ja, wie sieht es aus mit Durchschnitt?

Nun, bei deterministischen Automaten ist das leicht, wiederum.

Ich schreibe jetzt mal die Konstruktion für reguläre Sprachen auf, wir haben ja auch gerade über dich,

wir haben eine Legation auf regulären Sprachen, ich will jetzt also,

ich will jetzt also von zwei regulären Sprachen R und S den Durchschnitt bilden.

Das kann ich einfach per demokrits.

Das sind diejenigen, die weder von nicht R noch von nicht S akzeptiert werden.

Das ist dann glückwürdig, denn da kommt man, dass das der Durchschnitt von R und S ist.

Es ist noch ein bisschen die Frage, wie gut das wirklich funktioniert werden,

weil wir hier ja nicht determinismus reinbringen.

Gut, wir wissen, wir können jede reguläre Sprache durch einen deterministischen Automaten akzeptieren,